#include <iostream>
#define DEFAULT_SIZE 100
#define EXTEND_SIZE 2
#define EMPTY_VALUE (-1)
#define RIGHT_CHILD(x) ((x)*(2)+1)
#define LEFT_CHILD(x) (x)*(2)
#define PARENT_NODE(x) (x)/(2)

using namespace std;

class PriorityQueue{
private:
	int *queue;
	int size; // size of queue
	int length; // current legnth of queue

	void extendsQueueSize(){
		size *= EXTEND_SIZE;
		int *newQueue = new int[size];
		memset(newQueue, EMPTY_VALUE, size);
		for (int i = 0; i < size / EXTEND_SIZE + 1; i++){
			newQueue[i] = queue[i];
		}
		queue = newQueue;
		delete[] newQueue;
	}
	bool isEmpty(){
		return length == 0;
	}
	bool isFull(){
		return length >= size;
	}
	void swap(int &x, int &y) {
		int temp = x;
		x = y;
		y = temp;
	}

public:
	PriorityQueue() : PriorityQueue(DEFAULT_SIZE) { }
	PriorityQueue(int size){
		length = 0;
		this->size = size < DEFAULT_SIZE ? DEFAULT_SIZE : size;
		queue = new int[this->size];
		memset(queue, EMPTY_VALUE, size);
	}
	~PriorityQueue(){
		delete[] queue;
	}
	int pop(){
		if (isEmpty()){
			cout << "IndexBoundsException" << endl;
			return -1;
		}

		int returnValue = queue[1];
		queue[1] = queue[length];
		queue[length] = EMPTY_VALUE;
		
		int tempPos = 1;
		while (true){
			if (queue[LEFT_CHILD(tempPos)] == EMPTY_VALUE && queue[RIGHT_CHILD(tempPos)] == EMPTY_VALUE) {
				break;
			}
			else if (queue[RIGHT_CHILD(tempPos)] == EMPTY_VALUE ||
				queue[LEFT_CHILD(tempPos)] > queue[RIGHT_CHILD(tempPos)]) {
				swap(queue[PARENT_NODE(tempPos)], queue[LEFT_CHILD(tempPos)]);
				tempPos = LEFT_CHILD(tempPos);
			}
			else if (queue[LEFT_CHILD(tempPos)] == EMPTY_VALUE ||
				queue[LEFT_CHILD(tempPos)] < queue[RIGHT_CHILD(tempPos)]) {
				swap(queue[PARENT_NODE(tempPos)], queue[RIGHT_CHILD(tempPos)]);
				tempPos = RIGHT_CHILD(tempPos);
			}
		}

		return returnValue;
	}
	void push(int value){
		if (isFull()) { extendsQueueSize(); }

		// insert the value into terminal node
		this->queue[++length] = value;
		if (length == 1) { return; }

		// insert value into it's own position
		int tempPos = length;
		while (true){
			if (queue[PARENT_NODE(tempPos)] > queue[tempPos]) { break; }
			else if (queue[PARENT_NODE(tempPos)] < queue[tempPos]) {
				swap(queue[PARENT_NODE(tempPos)], queue[tempPos]);
				//int tempValue = queue[PARENT_NODE(tempPos)];
				//queue[PARENT_NODE(tempPos)] = queue[tempPos];
				//queue[tempPos] = tempValue;
				tempPos = PARENT_NODE(tempPos);
				if (tempPos == 1) break;
			}
			else {
				cout << "SameValueException : " << value << endl;
				return;
			}
		}
	}

	int getMax(){
		if (isEmpty()){
			cout << "EmptyCollectionException" << endl;
			return EMPTY_VALUE;
		}
		return queue[1];
	}
};

int main(){
	PriorityQueue p(1000);
	p.push(1);
	p.push(3);
	p.push(2);
	p.push(5);
	p.push(6);
	cout << p.pop() << endl;
	return 0;
}